It is widely used an information processing apparatus having a hierarchical cache memory configuration, in which a secondary cache memory is provided between a main memory and a plurality of processors each provided with a primary cache memory. Since a plurality of cache memories exist hierarchically in such an information processing apparatus, it is indispensable to ensure consistency of data.
In order to ensure consistency of data, it is an important factor to satisfy multi-level inclusion. The multi-level inclusion means that a secondary cache memory is placed in a state in which the secondary cache memory contains the same data as the data stored in the primary cache memories in the processors.
To satisfy the multi-level inclusion, there is proposed a technique of associating the memory block of the data stored in each primary cache memory and the memory block of the data stored in a secondary cache memory with each other. For example, refer to the following related-art document (hereinafter simply referred to as “Kessler”).
R. Kessler, R. Jooss, A. Lebeck, M. Hill, “Inexpensive Implementation of Set-Associative,” 16th ISCA, May 1989, pp. 131-139
In a system satisfying the multi-level inclusion, when data is read from a secondary cache memory, a plurality of areas in the secondary cache memory need to be searched to determine whether or not the corresponding data is stored at the read address. As exemplary algorithm for performing such search, Kessler proposes simple sequential search, MRU (Most Recently Used) and Partial Compare.
In the information processing apparatus having a plurality of processors each provided with a primary cache memory and a secondary cache memory, preferably improvement in the processing speed and downsizing of circuitry are satisfied at the same time. However, in the technique disclosed in Kessler, the memory block in the secondary cache memory is always searched starting at the top address of the memory block, and thus, it takes much time in determining whether or not the data to be read is stored in the secondary cache memory.
The algorithms of MRU and Partial Compare for speeding up data search in a plurality of memory blocks in the secondary cache memory leads to a complicated hardware mechanism.